package me.mingshan.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/description/
 * <p>
 * 给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
 * <p>
 * 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
 *
 * @author hanjuntao
 * @date 2025/9/1 0001
 */
public class L_1457_二叉树中的伪回文路径 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(3);
        root.right = new TreeNode(1);

        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(1);

        root.right.right = new TreeNode(1);

        //       2
        //      3   1
        //    3  1    1
        System.out.println(pseudoPalindromicPaths(root));  // 2
    }

    /**
     * 递归DFS解法
     * <p>
     * 思路：
     * 1. 递归遍历二叉树，将一个路径节点值加入缓存中，如果重复的节点值，缓存的value 加1
     * 2. 判断当前路径（cache）是否是伪回文, 如果是则计数器加1
     *
     *
     * 注意递归回溯问题
     *
     * <p>
     * 判断当前路径是否是伪回文
     * <p>
     * 所谓伪回文，就是路径经过的节点值排列中，存在一个回文序列
     * <p>
     * 只需要检测奇数个数字的个数，最多只能有一个数字出现奇数次
     *
     * @param root
     * @return
     */
    public static int pseudoPalindromicPaths(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Map<Integer, Integer> cache = new HashMap<>();
        AtomicInteger result = new AtomicInteger(0);

        dfs(root, cache, result);
        return result.get();
    }

    private static void dfs(TreeNode root, Map<Integer, Integer> cache,
                            AtomicInteger result) {
        if (root == null) {
            return;
        }

        cache.put(root.val, cache.getOrDefault(root.val, 0) + 1);

        if (root.left == null && root.right == null) {
            // 判断当前路径是否是伪回文
            boolean x = isPseudoPalindromicPath(cache);
            if (x) {
                result.incrementAndGet();
            }

            // 回溯
            cache.put(root.val, cache.get(root.val) - 1);
            return;
        }

        dfs(root.left, cache, result);
        dfs(root.right, cache, result);
        // 回溯
        cache.put(root.val, cache.get(root.val) - 1);
    }

    /**
     * 判断当前路径是否是伪回文
     * <p>
     * 所谓伪回文，就是路径经过的节点值排列中，存在一个回文序列
     * <p>
     * 只需要检测奇数个数字的个数，最多只能有一个数字出现奇数次
     *
     * @param cache
     * @return
     */
    private static boolean isPseudoPalindromicPath(Map<Integer, Integer> cache) {
        // 计算出现奇数次的数字个数
        int oddCount = 0;
        for (int count : cache.values()) {
            if (count % 2 != 0) {
                oddCount++;
            }
        }

        // 回文序列的条件：最多只能有一个数字出现奇数次
        return oddCount <= 1;
    }
}
